/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-k-sorted-arrays
   @Language: C++
   @Datetime: 19-04-28 15:01
   */

class Solution {
	struct Node{
		int value, array, index;
		Node(int val, int arr, int idx):value(val),array(arr),index(idx){}
		bool operator<(const Node &a)const{
			return value>a.value; // mini heap
		}
	};
public:
	/**
	 * @param arrays: k sorted integer arrays
	 * @return: a sorted array
	 */
	vector<int> mergekSortedArrays(vector<vector<int> > &arrays) {
		// write your code here
		vector<int> res;
		priority_queue<Node> heap;	//mini heap
		for(int i=0; i<arrays.size(); ++i)
			if(arrays[i].size()) heap.push(Node(arrays[i][0],i,1));
		for(; heap.size(); heap.pop()){
			const Node &a=heap.top();
			res.push_back(a.value);
			if(a.index<arrays[a.array].size())
				heap.push(Node(arrays[a.array][a.index],a.array,a.index+1));
		}
		return res;
	}
};
